#include <utils/sorted_array.h>
#include <mm/kmalloc.h>
#include <utils/debug.h>

int8 default_compare(item a, item b) {
    if (a < b) {
        return -1;
    }
    if (a == b) {
        return 0;
    }
    // a > b
    return 1;
}

struct sorted_array sorted_array_create(uint32 max_size, int8 (*compare)(item, item)) {
    struct sorted_array array;
    array.array = kmalloc(max_size * sizeof(void*));
    array.count = 0;
    array.max_size = max_size;
    array.compare = compare;
    return array;
}

struct sorted_array sorted_array_create_in(item* array, uint32 max_size, int8 (*compare)(item, item)) {
    struct sorted_array a;
    a.array = array;
    a.count = 0;
    a.max_size = max_size;
    a.compare = compare;
    return a;
}

void sorted_array_destroy(struct sorted_array *array) {
    kfree(array->array);
}

void sorted_array_insert(struct sorted_array *array, item data) {
    assert(array->compare && "Comparator not set for sorted array");
    uint32 idx = 0;
    while (idx < array->count && array->compare(array->array[idx], data) < 0)
        idx ++;
    if (idx == array->count) {
        array->array[array->count++] = data;
    } else {
        item t = array->array[idx];
        array->array[idx] = data;
        while (idx < array->count) {
            idx ++;
            item t2 = array->array[idx];
            array->array[idx] = t;
            t = t2;
        }
        array->count++;
    }
}

item sorted_array_get(struct sorted_array *array, uint32 idx) {
    assert(idx < array->count);
    return array->array[idx];
}

void sorted_array_remove(struct sorted_array *array, uint32 idx) {
    assert(idx < array->count);
    
    while (idx < array->count) {
        array->array[idx] = array->array[idx + 1];
        idx++;
    }
    array->count--;
}

// NOTE: this algo can be used for any array. We may need to move it elsewhere in the future
uint32 binary_search(void** array, void* data, uint32 left, uint32 right, int8 (*compare)(void*, void*)) {
    if (left > right) {
        // left index just passed right index without finding it
        return -1; // NOT FOUND
    }
    uint32 middle = (left + right) / 2;
    int8 comparison = compare(data, array[middle]);
    if (comparison == 0) {
        // FOUND IT!
        return middle;
    }
    if (comparison > 0) {
        // data > middle, look right
        return binary_search(array, data, middle+1, right, compare);
    }
    // data < middle, look left
    return binary_search(array, data, left, middle, compare);
    
}

uint32 sorted_array_find(struct sorted_array* array, item data) {
    assert(array);
    assert(array->compare);
    return binary_search(array->array, data, 0, array->count - 1, array->compare);
}





